package com.ztom.top100;

/**
 * 买卖股票的最佳时机
 * <p>
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 *
 * @author ZhangTao
 */
public class Code45MaxProfit {

    public class Info {
        /**
         * [0, i] 天的最小价格
         */
        private int minPrice;
        /**
         * [0, i] 天的最大利润
         */
        private int maxProfile;

        public Info(int minPrice, int maxProfile) {
            this.minPrice = minPrice;
            this.maxProfile = maxProfile;
        }
    }

    /**
     * 尝试
     *
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        return process(prices, prices.length - 1).maxProfile;
    }

    private Info process(int[] prices, int i) {
        if (i == 0) {
            return new Info(prices[0], 0);
        }

        // 与前一天相比
        Info pre = process(prices, i - 1);
        int minPrice = Math.min(prices[i], pre.minPrice);
        int maxProfile = Math.max(prices[i] - minPrice, pre.maxProfile);
        return new Info(minPrice, maxProfile);
    }

    /**
     * dp
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            dp[i] = Math.max(prices[i] - minPrice, dp[i - 1]);
        }

        return dp[n - 1];
    }

    /**
     * 滚动数组
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        // 第 1 天情况
        int minPrice = prices[0];
        int maxProfile = 0;
        // 第 i 天情况
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            maxProfile = Math.max(prices[i] - minPrice, maxProfile);
        }

        return maxProfile;
    }
}
